import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/18 9:35
 * @description 字典序排数 深度优先遍历 通过迭代方式实现 O(n) + O(1)
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.lexicalOrder(13);
    }
    public List<Integer> lexicalOrder(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        int number = 1;
        for (int i = 0; i < n; i++) {
            ret.add(number);
            if (number * 10 <= n) {
                number *= 10;
            } else {
                while (number % 10 == 9 || number + 1 > n) {
                    number /= 10;
                }
                number++;
            }
        }
        return ret;
    }
}
